package com.lagou.advance;

public class Sort {

    public static void QuickSort(int[] arr, int lft, int rgt) {
        if(lft >= rgt) return;

        int base = arr[lft];
        int i = lft;
        int j = rgt;
        while (i < j) {
            while (arr[j] >= base &&  i < j) {
                j--;
            }
            while (arr[i] <= base &&  i < j) {
                i++;
            }

            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;

        }

        arr[lft] = arr[i];
        arr[i] = base;
        QuickSort(arr, lft, i - 1);
        QuickSort(arr, j + 1, rgt);
    }

    public static void main(String[] args) {
        int[] arr = new int[]{2,5,3,1,6,7,4};
//        6，5，6，7，4
//        7 6 5 4 3 2 1
        QuickSort(arr, 0, arr.length - 1);

        for (int v :
                arr) {
            System.out.println(v);
        }
    }

}
